#!/usr/bin/python3
# _*_ coding: utf-8 _*_
#
# Copyright (C) 2024 - 2024 heihieyouheihei, Inc. All Rights Reserved 
#
# @Time    : 2024/8/16 22:38
# @Author  : Yuyun
# @File    : 最长子字符串长度_字符o.py
# @IDE     : PyCharm


"""
题目描述：
给你一个字符串s，字符串s首尾相连成一个环形，请你在环中找出o字符出现了偶数次最长子字符串的长度。

输入描述：
输入是一串小写字母组成的字符串
输出描述：
输出是一个整数 补充说明：
1<=s.length <=5x10^5 s只包含小写英文字母收起

示例1
输入： alolobo
输出：6
说明：
最长子字符串之一"是"alolob"，它包含'o' 2个
 示例2
输入： 1ooxdolx
输出： 7
说明：
最长子字符串是“oxdolxl”，由于是首尾连接在一起的，所以最后一个'x"和开头的是连接在一起的，
此字符串包含2个’o‘。
示例3
输入： bcbcbc
输出：6
说明：
这个示例中，字符串“bcbcbc”本身就是最长的，因为'o'都出现了0

"""


def find_longest_substring_with_even_o(s):
    # 复制一份字符串并拼接到其后
    ss = s + s
    n = len(s)
    max_length = 0
    start, end = 0, 0  # 用于记录最长子字符串的起始和结束位置（在ss中的位置）
    # 使用字典记录前缀和中'o'的奇偶性及其对应的最后出现位置
    prefix_sum = {0: -1}
    count = 0

    for i in range(2 * n):
        # 更新'o'的个数（模2）
        if ss[i] == 'o':
            count = (count + 1) % 2

            # 如果之前存在相同的前缀和，则计算当前子字符串的长度
        if count in prefix_sum:
            # 注意，由于我们复制了字符串，所以实际长度要减去重复的部分
            # 并且要调整起始位置到原始字符串s的范围内
            length = i - prefix_sum[count]
            if length > max_length:
                max_length = length
                # 更新最长子字符串的起始和结束位置（在s中的位置）
                # 注意：由于ss是s的重复，所以实际位置需要取模n
                start_pos = prefix_sum[count] % n
                end_pos = (i - 1) % n  # 减1是因为我们不想包含当前这个字符（它可能不在s内）
                if end_pos < start_pos:  # 处理跨越原始字符串末尾的情况
                    end_pos += n
                start, end = start_pos, end_pos
        else:
            # 如果不存在，则记录当前前缀和首次出现的位置
            prefix_sum[count] = i

            # 截取并返回最长子字符串（注意：这里返回的是s中的子字符串）
    return s[start:end + 1]


# 测试样例
print(find_longest_substring_with_even_o("alolobo"))  # 输出: "alolob" 或其他包含偶数个'o'的等价子字符串
print(find_longest_substring_with_even_o("1ooxdolx"))  # 输出: "oxdolx"
print(find_longest_substring_with_even_o("bcbcbc"))  # 输出: "bcbcbc"（因为'o'未出现，整个字符串都符合条件）
